#include <iostream>
#include <vector>
using namespace std;


struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
		val(x), left(NULL), right(NULL) {
	}
};

void find(TreeNode* root, int val,vector<TreeNode*> &v)
{
	if (root->val == val)
		v.push_back(root);
	TreeNode* left = NULL;
	TreeNode* right = NULL;
	if (root->left != NULL)
		find(root->left, val,v);
	if (root->right != NULL)
		find(root->right, val,v);
	
}

bool compare(TreeNode* r1, TreeNode* r2)
{
	if (r1->val != r2->val)
		return false;
	bool left = false, right = false;
	if (r1->left != NULL && r2->left != NULL)
		left = compare(r1->left, r2->left);
	else if (r2->left == NULL)//r1->left == NULL && 
		left = true;
	else return false;
	if (r1->right != NULL && r2->right != NULL)
		right = compare(r1->right, r2->right);
	else if (r2->right == NULL)//r1->right == NULL && 
		right = true;
	else return false;
	return left && right;
}


bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
	vector<TreeNode*> root_v;
	if (pRoot1 == NULL || pRoot2 == NULL) return false;
	find(pRoot1, pRoot2->val,root_v);
	if (root_v.size() == 0) return false;
	for (int i = 0; i < root_v.size(); ++i)
	{
		if (compare(root_v[i], pRoot2))
			return true;
	}
	return false;
}


//int main()
//{
//	TreeNode* root1 = new TreeNode(0);
//	TreeNode* p1 = root1;
//	bool flag = true;
//	for (int i = 1; i < 10; ++i)
//	{
//		TreeNode* left = new TreeNode(i);
//		TreeNode* right = new TreeNode(i + 1);
//		p1->left = left;
//		p1->right = right;
//		if (flag)
//		{
//			flag = false;
//			p1 = p1->right;
//		}
//		else
//		{
//			flag = true;
//			p1 = p1->left;
//		}
//	}
//	TreeNode* root2 = root1->right->left;
//	root2->right->left = NULL;
//	root2->right->right = NULL;
//
//	cout << HasSubtree(root1, root2);
//
//	return 0;
//}